package noth.li.sort;


/**
 * 快速排序
 * 一、快速排序的实现逻辑
 * 1.选中一个基准数(通常以数组第一个数字为基准数
 * 2.左侧、右侧各定义一个指针
 * 3.左侧指针从左至右寻找大于基准数的
 * 4.右侧指针从右至左寻找小于基准数的
 * 5.右侧指针先动,寻找小于基准数的
 * 6.找到小于基准数的时候停止
 * 7.左侧指针从左至右寻找大于基准数的
 * 8.找到大于基准数的时候停止
 * 9.左侧指针指向的与右侧指针指向的交换值
 * 10.左右侧指针继续移动,当两个指针指向同一个下标的时候
 * 11.指针指向的数与基准数交换位置
 * 12.所有时候,左侧指针的下标都要大于右侧指针的下标
 * 13.第一次循环结束后,基准数左侧的数都比基准数小,基准数右侧的数都比基准数大
 * 14.分别对基准数左侧的与基准数右侧的递归调用方法即可
 *
 * 二、
 * 快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。
 * 但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，
 * 比复杂度稳定等于 O(nlogn) 的归并排序要小很多。
 * 所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {7, 5, 88, 6, 99, 55, 22, 35, 57, 89, 10, 999, 29, 762, 11, 22, 3, 45, 2, 2, 2, 2, 1, 3, 21, 1};

        //quickSortAsc(arr, 0, arr.length - 1);
        quickSortDesc(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }


    /**
     * 快速排序实现方法,升序
     *
     * @param arr   排序数组
     * @param left  从哪开始
     * @param right 到哪儿
     */
    public static void quickSortAsc(int[] arr, int left, int right) {

        //当left > right时,结束递归
        if (left > right)
            return;

        //定义两个变量记录left与right指向的下标
        //因为left和right变量会随着程序的运行而改变
        int left0 = left;
        int right0 = right;

        //记录基准数(通常为数组第一个数字
        int base = arr[left0];

        //循环让left和right寻找大于和小于基准数的数
        while (left < right) {
            //right先动,寻找小于基准数的数
            while (arr[right] >= base && left < right) {
                right--;
            }

            //left后动,寻找大于基准数的数
            while (arr[left] <= base && left < right) {
                left++;
            }

            //走到这,证明left和right都找到了对应的数
            //需要交换两个数的值
            //但left必须小于right才可以
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        //走到这,证明left和right指向了同一个下标
        //基准数归位,基准数与left与right指向的同一位置交换
        int temp = arr[left0];
        arr[left0] = arr[left];
        arr[left] = temp;

        //递归调用此方法,将基准数左侧的数变为有序
        quickSortAsc(arr, left0, left - 1);
        //递归调用此方法,将基准数右侧的数变为有序
        quickSortAsc(arr, left + 1, right0);
    }

    /**
     * 快速排序实现方法,降序
     *
     * @param arr   排序数组
     * @param left  从哪开始
     * @param right 到哪儿
     */
    public static void quickSortDesc(int[] arr, int left, int right) {

        //当left > right时,结束递归
        if (left > right)
            return;

        //定义两个变量记录left与right指向的下标
        //因为left和right变量会随着程序的运行而改变
        int left0 = left;
        int right0 = right;

        //记录基准数(通常为数组第一个数字
        int base = arr[left0];

        //循环让left和right寻找大于和小于基准数的数
        while (left < right) {
            //right先动,寻找大于基准数的数
            while (arr[right] <= base && left < right) {
                right--;
            }

            //left后动,寻找小于基准数的数
            while (arr[left] >= base && left < right) {
                left++;
            }

            //走到这,证明left和right都找到了对应的数
            //需要交换两个数的值
            //但left必须小于right才可以
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        //走到这,证明left和right指向了同一个下标
        //基准数归位,基准数与left与right指向的同一位置交换
        int temp = arr[left0];
        arr[left0] = arr[left];
        arr[left] = temp;

        //递归调用此方法,将基准数左侧的数变为有序
        quickSortDesc(arr, left0, left - 1);
        //递归调用此方法,将基准数右侧的数变为有序
        quickSortDesc(arr, left + 1, right0);
    }
}
